/**
 * @author DCSGO
 * @version 1.0
 */

/*
来自神策
给定一个数组arr，表示连续n天的股价，数组下标表示第几天
指标X︰任意两天的股价之和–此两天间隔的天数
比如
第3天，价格是10
第9天，价格是30
那么第3天和第9天的指标X = 10 + 30 - (9 - 3) = 34
返回arr上中最大的指标X
股价大于0 且要求时间复杂度不超过 O(N)

分析：
i j 表示任意两天 且 i < j
X = arr[i] + arr[j] - (j - i)
  = arr[i] + arr[j]- j + i
  = arr[i] + i + arr[j] - j

  现在我们只需要求出最大的 arr[i] + i 以及最大的 arr[j] - j
  就得出了答案X 但 i < j 所以我们不能分开遍历他们俩
  而应在遍历 j 的同时求出 X 并在适当时更新 i
  该如何做到呢?
  令 preBest = arr[i] + i
     ans 为最终解
  显然在第0天
    preBest = arr[0] + 0 = arr[0]
    ans = 0
  第1天
    ans = arr[0] + arr[1] - 1
    preBest = max(preBet,arr[1]+1)
  第2天
    ans = max(ans,preBest+arr[2]-2)
    preBest = max(preBest,arr[2]+2)

  ......

  第j天
    ans = max(ans,preBest+arr[j]-j)
    preBest = max(preBest,arr[j]+j)

  当 j == n 时我们也就得出了答案
*/
public class P3 {
    public static void main(String[] args) {
        //int[] arr = {1, 2, 3, 4, 5, 6, 7};//12
        int[] arr = {100, 0, 0, 0, 0, 0, 0};//99
        System.out.println(maxTarget(arr));
    }

    public static int maxTarget(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        int preBest = arr[0];
        int ans = 0;
        for (int j = 1; j < arr.length; j++) {
            //必须先更新 ans 若先更新 preBest 可能会出现 i >= j 的情况
            ans = Math.max(ans, preBest + arr[j] - j);
            preBest = Math.max(preBest, arr[j] + j);
        }
        return ans;
    }
}
